package  com.xj.datastructure.sort;
public class QuickSort{
	public static void main(String [] args){
		System.out.println("=========================");
		int []arr={3,5,6,1,4,8,9,2};
		QuickSort q=new QuickSort();
		q.qsort(arr,0,arr.length-1);
		for(int i=0;i<arr.length;i++){
			System.out.println(arr[i]);
		}
	}
	private int partition(int []arr,int low,int high){
		int tmp=arr[low];
		while(low<high){
			while(low<high && arr[high]>tmp){
				high--;
			}
			arr[low]=arr[high];
			while(low<high && tmp>arr[low]){
				low++;
			}
			arr[high]=arr[low];
		}
		arr[low]=tmp;
		return low;
	}
	private void qsort(int []arr,int low,int high){
		if(low<high){
			int partition=partition(arr,low,high);
			qsort(arr,low,partition-1);
			qsort(arr,partition+1,high);
		}
	}
}